/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package sorting;

import java.util.LinkedList;

/**
 *  A simple implementation of the Quicksort algorithm by, first developed by Tony Hoare in 1960 in the Sovjet union.
 *  The algorithm is a quick sorting algorithm using the divide-and-conquer methodology, 
 *  that sorts a list by selecting a pivot, then sorting everything
 *  lesser than the pivot to one side, and everything greater to the other.
 *  More information regarding the principles about the algorithm can be found here: <a href="http://en.wikipedia.org/wiki/Quicksort">Quicksort at Wikipedia</a>.
 * @author Pasta
 */
public class Quicksort {
    //Variable declaration
    private LinkedList<Double> data;
    private pivotPosition position; 
    //End of variable declaration
    /**
     * 
     */
    public enum pivotPosition {

        /**
         * Uses the first element of the list as candidate of pivot.
         */
        LEFTMOST,
        /**
         *  Uses `(array.size() - 1) / 2' as method to get the candidate of pivot.
         */
        CENTER,
        /**
         * Uses `((int)(Math.random() * 10 * array.size() % (array.size - 1))' as method to get the candidate of pivot. 
         */
        RANDOM,
        /**
         *
         */
        RIGHTMOST;
    }
    //Constructors
    /**
     * Constructor to add data as a linked list. Uses the default pivot type CENTER.
     * @param list 
     */
    public Quicksort(LinkedList<Double> list) {
        this(list, pivotPosition.CENTER);
    }
    /**
     * Constructor to add data as a linked list, and the choice of pivot type.
     * @param list The values to be sorted.
     * @param pos pivot position.
     */
    public Quicksort(LinkedList<Double> list, pivotPosition pos) {
        data = list;
        position = pos;
    }
    /**
     * Constructor to add data both as a double array and as a multi parameter input,
     * and the default pivot type CENTER.
     * @param values The values to be sorted.
     */
    public Quicksort(double ... values) {
        this(pivotPosition.CENTER, values);
    }
    /**
     * Constructor to add data both as a double array and as a multi parameter input,
     * and the default pivot type CENTER.
     * @param p pivot position.
     * @param values The values to be sorted.
     */
    public Quicksort(pivotPosition p, double ... values) {
        data = new LinkedList<Double>();
        for(double d : values) {
            data.add(d);
        }
    }
    //End of constructors
    
    
    private LinkedList<Double> sort(LinkedList<Double> list) {
        Double pivot;
        if(list.size() < 1) {
            return list;
        }
        pivot = getPivot(list);
        LinkedList<Double> gt, lt;
        gt = new LinkedList<Double>();
        lt = new LinkedList<Double>();
        for(Object o : list) {
            Double test = (Double) o;
            if(test <= pivot) {
                lt.add(test);
            } else {
                gt.add(test);
            }
        }
        return concatenate((LinkedList) sort(lt), pivot, (LinkedList) sort(gt));
    }
    /**
     * Sorts the internal object data.
     * @return A sorted list of all the elements.
     */
    public LinkedList<Double> sort() {
        return sort(data);
    }
    /**
     * 
     * @param less List containing all the elements lesser than the pivot.
     * @param pivot The pivot itself.
     * @param greater List containing all the elements greater than the pivot.
     * @return A concatenated list of the elements.
     */
    private LinkedList<Double> concatenate(LinkedList<Double> less, Double pivot, LinkedList<Double> greater) {
        LinkedList<Double> ret = new LinkedList<Double>();
        if(less.size() > 0) {
            for(Object o : less) {
                ret.add((Double) o);
            }
        }
        ret.add(pivot);
        if(greater.size() > 0) {
            for(Object o : greater) {
                ret.add((Double) o);
            }
        }
        return ret;
    }
    /**
     * 
     * @param list The list that the sort function needs a pivot from.
     * @return The pivot.
     */
    private double getPivot(LinkedList<Double> list) {
        switch(position) {
            case LEFTMOST:
                return list.removeFirst();
            case CENTER:
                return list.remove();
            case RANDOM:
                return list.remove(((int)(Math.random() * 10 * list.size() % (list.size() - 1))));
            case RIGHTMOST:
                return list.removeLast();
           default:
               throw new RuntimeException("Should never happen");
        }
    }
}